백준 17144번
오늘 풀어본 문제는 백준의 17144번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 $R \times C$ 인 격자판으로 나타냈고, $1 \times 1$ 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. $(r, c)$ 는 $r$ 행 $c$ 열을 의미한다.
공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, $(r, c)$ 에 있는 미세먼지의 양은 $A_{r,c}$ 이다.
1초 동안 아래 적힌 일이 순서대로 일어난다.
-
미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
-
$(r, c)$ 에 있는 미세먼지는 인접한 네 방향으로 확산된다.
-
인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
-
확산되는 양은 $A_{r,c}/5$ 이고 소수점은 버린다.
-
$(r, c)$ 에 남은 미세먼지의 양은 $A_{r,c} - (A_{r,c}/5) \times$ (확산된 방향의 개수) 이다.
-
-
공기청정기가 작동한다.
-
공기청정기에서는 바람이 나온다.
-
위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
-
바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
-
공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.
-
다음은 확산의 예시이다.
왼쪽과 위쪽에 칸이 없기 때문에, 두 방향으로만 확산이 일어났다.
인접한 네 방향으로 모두 확산이 일어난다.
공기청정기가 있는 칸으로는 확산이 일어나지 않는다.
공기청정기의 바람은 다음과 같은 방향으로 순환한다.
방의 정보가 주어졌을 때, $T$ 초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.
입력
첫째 줄에 $R$, $C$, $T$ $(6 \leq R, C \leq 50, 1 \leq T \leq 1,000)$ 가 주어진다.
둘째 줄부터 $R$ 개의 줄에 $A_{r,c}$ $(-1 \leq A_{r,c} \leq 1,000)$ 가 주어진다. 공기청정기가 설치된 곳은 $A_{r,c}$ 가 $-1$ 이고, 나머지 값은 미세먼지의 양이다. $-1$ 은 $2$ 번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다.
출력
첫째 줄에 $T$ 초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
풀이과정
1번째 시도
문제를 처음보고 살짝 당황했다. 길이가 굉장히 길었기 떄문이다. 하지만 천천히 읽어보니 간단한 구현문제라는 것을 알 수 있었다. 문제에서 $R$ 과 $C$의 크기도 그리 크지 않았기 때문에 우선 떠오르는 대로 간단하게 구현해보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
int R, C;
int house[50][50] = { 0, };
int propagate[50][50] = { 0, };
pair<int, int> upperCleaner = make_pair(-1, -1);
pair<int, int> lowerCleaner = make_pair(-1, -1);
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
void oneSecondLater(void);
void spread(void);
void cleanerWork(void);
bool isInRange(int r, int c);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> R >> C >> T;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
cin >> house[i][j];
if (house[i][j] == -1) {
if (upperCleaner.first == -1 && upperCleaner.second == -1) {
upperCleaner = make_pair(i, j);
}
else {
lowerCleaner = make_pair(i, j);
}
}
}
}
for (int second = 0; second < T; second++) {
oneSecondLater();
}
int answer = 2;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
answer += house[i][j];
}
}
cout << answer;
return 0;
}
void oneSecondLater(void) {
spread();
cleanerWork();
}
void spread(void) {
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
propagate[i][j] = 0;
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
for (int dir = 0; dir < 4; dir++) {
int newY = i + dy[dir];
int newX = j + dx[dir];
if (isInRange(newY, newX) == true && house[newY][newX] != -1) {
propagate[newY][newX] += (house[i][j] / 5);
propagate[i][j] -= (house[i][j] / 5);
}
}
}
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
house[i][j] += propagate[i][j];
}
}
}
void cleanerWork(void) {
int dustToPush = 0;
for (int column = 1; column < C; column++) {
swap(dustToPush, house[upperCleaner.first][column]);
}
for (int row = upperCleaner.first - 1; row >= 0; row--) {
swap(dustToPush, house[row][C - 1]);
}
for (int column = C - 2; column >= 0; column--) {
swap(dustToPush, house[0][column]);
}
for (int row = 1; row < upperCleaner.first; row++) {
swap(dustToPush, house[row][0]);
}
dustToPush = 0;
for (int column = 1; column < C; column++) {
swap(dustToPush, house[lowerCleaner.first][column]);
}
for (int row = lowerCleaner.first + 1; row < R; row++) {
swap(dustToPush, house[row][C - 1]);
}
for (int column = C - 2; column >= 0; column--) {
swap(dustToPush, house[R - 1][column]);
}
for (int row = R - 2; row > lowerCleaner.first; row--) {
swap(dustToPush, house[row][0]);
}
}
bool isInRange(int r, int c) {
if (r < 0 || r > R - 1) {
return false;
}
else if (c < 0 || c > C - 1) {
return false;
}
else {
return true;
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
간만에 만난 단순 구현 문제였던 것 같다. 특별한 알고리즘 없이도 풀 수 있는 적당히 난이도의 맛있는 문제였던 것 같다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/17144